from typing import List


class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        works = [[difficulty[i], profit[i]] for i in range(len(difficulty))]
        works.append([0, 0]) # 下限
        works.append([100000, 100000]) # 上限
        works.sort(key = lambda it: it[0])

        # 计算在此难度下能获得的最大收益
        mp = 0
        for w in works:
            mp = max(mp, w[1])
            w[1] = mp

        worker.sort()

        wi = 0 # work i
        ti = 0 # tuple i
        r = 0
        while wi < len(worker):
            wd = worker[wi] # work diff
            while ti < len(works):
                if wd < works[ti][0]: # 如果太难，说明最大收益在上一步
                    r += works[ti - 1][1]
                    break
                ti += 1
            wi += 1
        return r

solu = Solution()
# print(solu.maxProfitAssignment(difficulty=[2,4,6,8,10], profit=[10,20,30,40,50], worker=[4,5,6,7]))
# print(solu.maxProfitAssignment(difficulty=[68,35,52,47,86], profit=[67,17,1,81,3], worker=[92,10,85,84,82])) # 324

print(solu.maxProfitAssignment(difficulty=[23,30,35,35,43,46,47,81,83,98],
    profit=[8,11,11,20,33,37,60,72,87,95],
    worker=[95,46,47,97,11,35,99,56,41,92])) # 553


# profit: 81 67 17 3  1

# diffcu: 47 68 35 86 52



# diff: 35, 47, 52, 68, 86
# prof: 17, 81, 1,  67, 3
#       17, 81, 81, 81, 81

# 92 85 84 82 10

# 81, 81, 81, 81, 0